#include<iostream>
using namespace std;
const int N=2e6+10;
char s[N];
bool st[N];
int n,q,l,r;
struct Node{
	int dt1;
	int num0,num1;
}tr[N];
void init(){
	for(int i=1;i<=n;i++){
		tr[i]=tr[i-1];
		if(s[i]=='1') tr[i].num1++;
		else tr[i].num0++;
		if(s[i-2]=='0'&&s[i-1]=='1'&&s[i]=='0') tr[i].dt1++,st[i-1]=1;
	}
//	if(s[n]=='1'&&s[1]=='0'&&s[n-1]=='0') st[n]=1,tr[i].dlt++;
}
int main(){
	cin>>n>>q;
	scanf("%s",s+1);
	init();
//	for(int i=1;i<=n;i++) cout<<tr[i].dt1<<' '<<tr[i].num0<<' '<<tr[i].num1<<endl;
	while(q--){
		cin>>l>>r;
		Node t;
		t.num0=tr[r].num0-tr[l-1].num0;
		t.num1=tr[r].num1-tr[l-1].num1;
		t.dt1=tr[r].dt1-tr[l-1].dt1;
		if(st[l]) t.dt1--;
		if(st[l-1]) t.dt1--;
//		if(st[r]) t.dt1--;
		if(s[r]=='1'&&s[r-1]=='0'&&s[l]=='0') t.dt1++;
		if(s[l]=='1'&&s[l+1]=='0'&&s[r]=='0') t.dt1++;
		int dq=t.dt1*2;
		int num=t.num1-t.dt1;
		dq+=(num/2)+(num%2)*2;
		if(dq>=t.num0) cout<<0<<endl;
		else cout<<(t.num0-dq)/3<<endl;
	}
	return 0;
}
